package com.leetcode.algorithm.y22.m07.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 110. 平衡二叉树
 * 
 * https://leetcode.cn/problems/balanced-binary-tree/
 * 
 * @author jie.deng
 *
 */
class Question0110Solution01 {

	public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		if (root.left == null && root.right == null) {
			return true;
		}
		if (!isBalanced(root.left)) {
			return false;
		}
		if (!isBalanced(root.right)) {
			return false;
		}
		int heightL = getHeight(root.left);
		int heightR = getHeight(root.right);
		return Math.abs(heightL - heightR) <= 1;
	}

	private int getHeight(TreeNode node) {
		if (node == null) {
			return 0;
		}
		return 1 + Math.max(getHeight(node.left), getHeight(node.right));
	}

}